package basic.study.algorithms.solution.recall;

/**
 * @author Kevin
 * @date 2020/2/17 20:48
 * 0-1 背包问题
 * 我们有一个背包，背包总的承载重量是 Wkg。现在我们有 n 个物品，每个物品的重量不等，并且不可分割。我们现在期望选择几件物品，装载到背包中。在不超过背包所能装载重量的前提下，如何让背包中物品的总重量最大？
 *
 */
public class Bag {
    public static int maxW = Integer.MIN_VALUE;//存储背包中物品总重量的最大值
    // cw表示当前已经装进去的物品的重量和；i表示考察到哪个物品了
    // w背包重量；items表示每个物品的重量；n表示物品个数
    // 假设背包可承受重量100，物品个数10，物品重量存储在数组a中，那可以这样调用函数
    // f(0, 0, a, 10, 100)
    public static void f(int i, int cw, int[] items, int n, int w) {
        //函数入口处的 if 分支表明递归结束条件，并保证 maxW 跟踪所有选择中的最大值
        if (cw == w || i == n) {// cw==w表示装满了;i==n表示已经考察完所有的物品
            if (cw > maxW) maxW = cw;
            return ;
        }
        f(i+1, cw, items, n, w);//递归调用表示不选择当前物品，直接考虑下一个（第 i+1 个），故 cw 不更新
        if (cw + items[i] <= w) {// 已经超过可以背包承受的重量的时候，就不要再装了
            f(i+1, cw+items[i], items, n, w);//递归调用表示选择了当前物品，故考虑下一个时，cw 通过入参更新为 cw + items[i]
        }
    }

    //引入价值后

    private int maxV = Integer.MIN_VALUE; // 结果放到maxV中
    private int[] weight = {2,2,4,6,3};  // 物品的重量
    private int[] value = {3,4,8,9,6}; // 物品的价值
    private int n = 5; // 物品个数
    private int w = 9; // 背包承受的最大重量
    public void f(int i, int cw, int cv) { // 调用f(0, 0, 0)
        if (cw == w || i == n) { // cw==w表示装满了，i==n表示物品都考察完了
        if (cv > maxV) maxV = cv;
        return;
        }
        f(i+1, cw, cv); // 选择不装第i个物品
        if (cw + weight[i] <= w) {
        f(i+1,cw+weight[i], cv+value[i]); // 选择装第i个物品
        }
        }
}
